#include<stdio.h>
#include<conio.h>
#include<alloc.h>

void swap(int *x,int *y)
{
 int temp;
 temp=*x;
 *x=*y;
 *y=temp;
}

void bubsort(int *x,int n)
{
  int i,j;

  for(i=1;i<n;i++)
   for(j=n-1;j>=i;j--)
    if (x[j]<x[j-1])
     swap(&x[j],&x[j-1]);
}

int binary(int a[],int n)
{
 int item,found=0,mid;
 int key,left,right;

 printf("\n\nItem: ");
 scanf("%d",&item);

 bubsort(a,n);

 left=0;
 right=n-1;
 while(left<=right && !found)
  {
   mid=(left+right)/2;
   key=a[mid];
   if(item==key)
    found=1;
   else
    {
     if(item>key) left=mid+1;
     else right=mid-1;
    }
  }

 if(found) return(mid+1);
 else return(0);

}

int linear(int *a,int n)
{
 int item,found=0,i;

 printf("\n\nItem: ");
 scanf("%d",&item);
 for(i=0;i<n && !found;i++)
  if(item==a[i]) found=1;

 if(found) return(i);
 else return(0);

}

void main()
{
 int *a,n,i;
 char choice;

 clrscr();
 printf("--- SEARCH ---\n");
 printf("No. of elements:");
 scanf("%d",&n);
 a=(int*)malloc(n*sizeof(int));
 printf("\nList Input\n");
 for(i=0;i<n;i++)
   scanf("%d",&a[i]);

 do
 {
  printf("\n---MENU---\n");
  printf("<L> . . . Linear search\n");
  printf("<B> . . . Binary search\n");
  printf("<V> . . . View array\n");
  printf("<X> . . . Exit\n\n");
  printf("Choice: ");
  choice=toupper(getche());
  switch(choice)
   {
    case 'B': 	i=binary(a,n);
		if(i) printf("Found!");
		else printf("Not found!");
		getch();
		break;

    case 'L':	i=linear(a,n);
		if(i)printf("Found at location %d",i-1);
		else printf("Not found.");
		printf("\n");
		getch();
		break;
    case 'V':   printf("\n\nArray\n");
		for(i=0;i<n;i++)
		 printf("%d ",a[i]);
		getch();
		break;
    case 'C':	clrscr();
		break;
   }
  printf("\n");
 }while(choice!='X');
}



